1. Field of Invention
The field of invention relate generally to communications switching networks and more particularly to systems and methods for upgrading scalable switching networks.
2. Description of Related Art
Switching networks with regular structure have been explored for many years. Conspicuous among them are the so-called fixed radix networks, which typically comprise n stages of rn switching elements with each switching element having a fanin and fanout of r, where r is the radix. The majority of past research has been focused on radix two networks that is where r=2. Goke and Lipovski in “Banyan Network for Partitioning Multiprocessor Systems,” proposed the Banyan network. Examples are illustrated in FIGS. 1A, 1B and 1C. FIG. 1A shows a 3-stage Banyan network with stages 101, 103, and 105 of switching elements. FIG. 1B shows a 4-stage Banyan network with stages 111, 113, 115 and 117. The Banyan network can be extended to other radixes such as a radix three network illustrated in FIG. 1C having three stages, stages 121, 123 and 125. This network actually finds its origin in the design of fast Fourier Transforms where it is also often termed a butterfly network. Patel in “Performance of Processor-Memory Interconnections for Multiprocessors” proposed the delta network shown in FIG. 1D with four stages, namely stages 131, 133, 135 and 137. The network shown in FIG. 1E is often called a crossover network shown here with four stages, stages 141, 143, 145 and 147. Lawrie in “Parallel Processing with a Perfect Shuffle,” uses the network shown in FIG. 1F, known as a perfect shuffle, which is often termed in the art as an Omega network, shown here with three stages, stages 151, 153, and 155. A nameless radix two network can be found in the bit order preserving fast Fourier transform architecture described in Oppenheim and Schaefer's text, Digital Signal Processing. This network is shown here with four stages (stages 161, 163, 165 and 167) in FIG. 1G and is referred to as a bit-order persevering (BOP) network for the purpose of this disclosure.
These traditional radix networks offer functional connectivity, but lack redundancy and fault tolerance. Many methods and architectures have been developed to extend fixed radix networks to add redundancy and fault tolerance. Hamid, Shiratori and Noguchi in “A new fast control mechanism for Benes rearrangeable interconnection network useful for supersystems,” extend the delta network (e.g., network 201) with a second delta network (e.g., network 203) into an architecture first suggested by Benes in “Permutation Groups, Complexes, and Rearrangeable Connecting Networks,” as shown in FIG. 2A. This can be reconfigured to show two Banyan networks (e.g., networks 211 and 213) coupled together as shown in FIG. 2B.
Further, Adams and Siegel in “The Extra Stage Cube: A Fault-Tolerant Interconnection Network for Supersystems,” teach the extra stage cube which resembles a Banyan network in FIG. 2C with an extra stage. Through the use of multiplexers 16 and demultiplexers 14, stage 10 and stage 12 can individually be enabled or bypassed giving fault tolerance to the entire network.
Kumar and Reddy in “Augmented shuffle-exchange multistage interconnection networks”, add fault tolerance and path redundancy to a Banyan network offering additional lateral paths (for example, paths 221, 223, 225 and 227) for signals to travel which is depicted in FIG. 2D, This augmented shuffle-exchange network (ASEN) increases fault tolerance and path redundancy at the expense of increased path blocking.
Another technique for augmenting fixed radix network designs is by overlaying a second network onto a preexisting design. By this method, the fault tolerance of a network can be increased. The simplest technique is dilation, which is simply the overlaying of the same network on itself. FIG. 3A shows a Banyan network like that depicted in FIG. 1B overlaid on top of a second identical Banyan network. In the traditional design, the external ports (e.g., ports 301 and 303) are not augmented in the process. However, some designs do incorporate it as shown in FIG. 3B compare with ports 311 and 313). In either case, the resultant network does increase the ability to tolerate a failure in an internal connection, but fails to compensate for any potential failure in a switching element.
This dilation technique is further refined by overlaying an upside-down version of the same network on top of itself. FIG. 4A depicts a Banyan network like that of FIG. 1B except upside-down, (shown with same reference number for the stages as FIG. 1B). Often in this technique, the connections depicted by the dotted line are often considered overly redundant and are omitted. The result is the network shown in FIG. 4B. Once again the external ports are usually not augmented, but can be. This new network does compensate for failures in switching elements.
A final extension of multistage interconnection design is the seldom used multidimensional version of the multistage interconnection network. Though not well known in switching applications, multidimensional interconnections are frequently used in signal processing. Specifically, in the design of fast Fourier transforms (FFT) multistage interconnection networks are used. Since fixed radix networks, in particular the butterfly/Banyan, are the essential building blocks of the FFT. Multidimensional extensions of the butterfly are the essential building blocks of multidimensional FFT. This is discussed in great detail in any standard multidimensional signal processing text such as Dudgeon and Mersereau's Multidimensional Signal Processing.